//正则表达式匹配
class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.size() , n = p.size();
        vector<vector<bool>> dp(m+1,vector<bool>(n+1));
        dp[0][0] = true;
        for(int i = 2 ; i <= n ; i += 2)
        {
            if(p[i-1] == '*') dp[0][i] = true;
            else break;
        }
        for(size_t i = 1 ; i <= m ; ++i)
        {
            for(size_t j = 1 ; j <= n ; ++j)
            {
                if(p[j-1] == '*')
                {
                    if(p[j-2] == '.')
                        dp[i][j] = dp[i][j-2] || dp[i-1][j];
                    else 
                        dp[i][j] = dp[i][j-2] || (s[i-1] == p[j-2] && dp[i-1][j]);
                }
                else 
                {   if(p[j-1] == '.')
                        dp[i][j] = dp[i-1][j-1];
                    else 
                        dp[i][j] = p[j-1] == s[i-1] && dp[i-1][j-1];
                }
            }
        }
        return dp[m][n];
    }
};

//交错字符串
class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        //1、预处理
        if(s1.size() + s2.size() != s3.size()) return false;
        s1 = ' ' + s1;
        s2 = ' ' + s2;
        s3 = ' ' + s3;
        //2、创建dp表
        int m = s1.size() , n = s2.size();
        vector<vector<bool>> dp(m,vector<bool>(n));
        //3、初始化
        dp[0][0] = true;
        for(size_t i = 1 ; i < m ; ++i )
        {
            if(s1[i] == s3[i]) dp[i][0] = true;
            else break;
        }
        for(size_t i = 1 ; i < n ; ++i)
        {
            if(s2[i] == s3[i]) dp[0][i] = true;
            else break;
        }
        //4、填表
        for(size_t i = 1 ; i < m ; ++i)
            for(size_t j = 1 ; j < n ; ++j)
                dp[i][j] = (s1[i] == s3[i+j] && dp[i-1][j]) || (s2[j] == s3[i+j] && dp[i][j-1]);
        //5、返回值
        return dp[m-1][n-1];
    }
};

//两个字符串的最小ASCLL删除和
class Solution {
public:
    int minimumDeleteSum(string s1, string s2) {
        int m = s1.size() , n = s2.size();
        //题目分析：找最小ASCLL值删除和，即找公共子序列中ASCLL码值最大的序列
        //1、创建dp表
        vector<vector<int>> dp(m+1,vector<int>(n+1));
        //3、填表
        for(size_t i = 1 ; i <= m ; ++i)
            for(size_t j = 1 ; j <= n ; ++j)
                dp[i][j] = s1[i-1] == s2[j-1] ? s1[i-1] + dp[i-1][j-1] : max(dp[i-1][j],dp[i][j-1]);
        //4、返回值
        int sum1 = 0 , sum2 = 0;
        for(auto& x : s1) sum1 += x;
        for(auto& x : s2) sum2 += x;
        return sum1 + sum2 -  2*dp[m][n];
    }
};

//最长重复子数组
class Solution {
public:
    int findLength(vector<int>& nums1, vector<int>& nums2) {
        //1、创建dp表
        int m = nums1.size() , n = nums2.size();
        vector<vector<int>> dp(m+1,vector<int>(n+1));
        int ret = 0;
        //2、填表
        for(size_t i = 1 ; i <= m ; ++i)
        {
            for(size_t j = 1 ; j <= n ; ++j)
            {
                dp[i][j] = nums1[i-1] == nums2[j-1] ? dp[i-1][j-1] + 1 : 0;
                ret = max(ret , dp[i][j]);
            }
        }
        return ret;
    }
};